<html>
<head><meta charset="utf-8"><title>Optimization of const array access · t-compiler/wg-mir-opt · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/index.html">t-compiler/wg-mir-opt</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html">Optimization of const array access</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="207455252"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207455252" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207455252">(Aug 19 2020 at 20:03)</a>:</h4>
<p>I'm trying to debug why <a href="https://godbolt.org/z/vM9zf5">https://godbolt.org/z/vM9zf5</a> does not const propegate <code>_2[_3]</code>to <code>12_i32</code>.<br>
Using -Zdump-mir on an example, reveals that only after <code>SimplifyCfg-after-remove-noop-landing-pads</code> does the <code>_2[_4]</code> get merged into bb0. My hypothesis was that the copy propegator only worked within a basic block. I therefore added a const prop pass right after this pass. That newly added pass however does nothing. Looking at the trace with <code>RUSTC_LOG=rustc_mir::transform::const_prop</code>reveals this </p>
<div class="codehilite"><pre><span></span><code>rustc_mir::transform::const_prop: visit_statement: _0 = _2[_4]
2020-08-19T19:46:27.419184Z TRACE rustc_mir::transform::const_prop: InterpCx operation failed: InterpErrorInfo { kind: tried to access an uninitialized local, backtrace: None }
2020-08-19T19:46:27.419187Z TRACE rustc_mir::transform::const_prop: propagation into _0 failed.
                        Nuking the entire site from orbit, it&#39;s the only way to be sure
</code></pre></div>


<p>For reference the bb looks like this:</p>
<div class="codehilite"><pre><span></span><code>    bb0: {
        StorageLive(_2);                 // scope 0 at src/test/mir-opt/const_array_index.rs:6:9: 6:12
        _2 = [const 12_i32, move _1];    // scope 0 at src/test/mir-opt/const_array_index.rs:6:15: 6:25
        _4 = const 0_usize;              // scope 1 at src/test/mir-opt/const_array_index.rs:7:9: 7:10
        _5 = const 2_usize;              // scope 1 at src/test/mir-opt/const_array_index.rs:7:5: 7:11
        _6 = const true;                 // scope 1 at src/test/mir-opt/const_array_index.rs:7:5: 7:11
        _0 = _2[_4];                     // scope 1 at src/test/mir-opt/const_array_index.rs:7:5: 7:11
        StorageDead(_2);                 // scope 0 at src/test/mir-opt/const_array_index.rs:8:1: 8:2
        return;                          // scope 0 at src/test/mir-opt/const_array_index.rs:8:2: 8:2
    }
</code></pre></div>


<p>I don't understand which uninitialized locals are being accessed. To me, both _2 and _4 are initialised.</p>



<a name="207493400"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207493400" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207493400">(Aug 20 2020 at 06:45)</a>:</h4>
<p>there may be more information earlier in the log. We do an initial analysis that figures out what locals to even propagate (if not they stay uninitialized). Can you check if there's more info about <code>_4</code> there?</p>



<a name="207493465"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207493465" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207493465">(Aug 20 2020 at 06:46)</a>:</h4>
<p>I'm guessing the mir at the const_prop stage still has a terminator between the assignment to _4 and the assignment to _0</p>



<a name="207517232"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207517232" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Wesley Wiser <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207517232">(Aug 20 2020 at 12:40)</a>:</h4>
<blockquote>
<p>My hypothesis was that the copy propegator only worked within a basic block.</p>
</blockquote>
<p>Yes, there are some cases where we only do propagation for values within the basic block they are assigned to. See <a href="https://github.com/rust-lang/rust/blob/1a22a0ff93d63f738151f096434e732466b4a42e/src/librustc_mir/transform/const_prop.rs#L977">https://github.com/rust-lang/rust/blob/1a22a0ff93d63f738151f096434e732466b4a42e/src/librustc_mir/transform/const_prop.rs#L977</a></p>



<a name="207735154"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207735154" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207735154">(Aug 22 2020 at 18:00)</a>:</h4>
<p>This is the full trace as well as the MIR const-prop is running on: <a href="https://gist.github.com/simonvandel/845ea852ac59ce0d6eed6db1d379eef5">https://gist.github.com/simonvandel/845ea852ac59ce0d6eed6db1d379eef5</a></p>
<p><a href="https://gist.github.com/simonvandel/845ea852ac59ce0d6eed6db1d379eef5#file-const_prop-trace-L11-L12">https://gist.github.com/simonvandel/845ea852ac59ce0d6eed6db1d379eef5#file-const_prop-trace-L11-L12</a> seems a bit weird to me. Why would const 12 be uninitialized?</p>



<a name="207735640"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207735640" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207735640">(Aug 22 2020 at 18:12)</a>:</h4>
<div class="codehilite"><pre><span></span><code>local _1 can&#39;t be const propagated because it&#39;s a function argument
visit_statement: _2 = [const 12_i32, move _1]
</code></pre></div>


<p>Evaluation of <code>_2</code> depends on <code>_1</code>, which is an function argument.</p>



<a name="207735805"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207735805" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207735805">(Aug 22 2020 at 18:16)</a>:</h4>
<p>Alright that does make sense</p>



<a name="207736162"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207736162" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207736162">(Aug 22 2020 at 18:25)</a>:</h4>
<p>So if I instead look at <a href="https://godbolt.org/z/c8o1rK">https://godbolt.org/z/c8o1rK</a><br>
Locally I get can get the array access const-propped if i add another run of the pass after <code>&amp;simplify::SimplifyCfg::new("after-remove-noop-landing-pads"),</code>. The question is if that is a good idea. The idea is that SimplifyCfg could potentially have merged bbs which enables const-prop to do more again</p>



<a name="207740843"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207740843" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207740843">(Aug 22 2020 at 20:26)</a>:</h4>
<p>yes, we are thinking about creating a meta-pass that runs several passes in a loop until a fixed point is reached</p>



<a name="207741037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207741037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207741037">(Aug 22 2020 at 20:32)</a>:</h4>
<p>Cool. Would that be a good candidate for a mir-opt issue on the issue tracker? I’m guessing with an overall design/mentoring it could be doable as a starter</p>



<a name="207741298"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207741298" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207741298">(Aug 22 2020 at 20:41)</a>:</h4>
<p>I read a paper about a dataflow framework that merges multiple of these optimization passes into one. It supposedly even allowed some optimizations that running the individual optimization passes after each other in fix point couldn't perform if I remember correctly.</p>



<a name="207741475"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207741475" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207741475">(Aug 22 2020 at 20:46)</a>:</h4>
<p><a href="https://scholar.google.com/scholar?hl=nl&amp;as_sdt=0%2C5&amp;q=dataflow+optimization&amp;btnG=#d=gs_qabs&amp;u=%23p%3DTN6oEBjNKC8J">https://scholar.google.com/scholar?hl=nl&amp;as_sdt=0%2C5&amp;q=dataflow+optimization&amp;btnG=#d=gs_qabs&amp;u=%23p%3DTN6oEBjNKC8J</a></p>
<p>Hoopl: Dataflow optimization made simple</p>



<a name="207741480"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207741480" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207741480">(Aug 22 2020 at 20:46)</a>:</h4>
<p>^ found it</p>



<a name="207743242"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207743242" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pachi <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207743242">(Aug 22 2020 at 21:39)</a>:</h4>
<p>IIRC <span class="user-mention" data-user-id="118594">@ecstatic-morse</span> did a lot of work on dataflow in Rust. They may be interested in that paper ^</p>



<a name="207744174"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207744174" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207744174">(Aug 22 2020 at 22:11)</a>:</h4>
<p>I read some parts of the paper used as a reference in the Hoopl paper. <a href="https://scholar.google.dk/scholar?q=Composing+dataflow+analyses+and+transformations.&amp;hl=da&amp;as_sdt=0&amp;as_vis=1&amp;oi=scholart">https://scholar.google.dk/scholar?q=Composing+dataflow+analyses+and+transformations.&amp;hl=da&amp;as_sdt=0&amp;as_vis=1&amp;oi=scholart</a></p>
<p>AFAIU it suggests making each pass modular in the sense that it receives a graph as input and can return a replacement graph. The framework can automatically interleave passes “depth first”. For example a const prop pass transforms “3 &lt; 4” into “true”. This new info is then used immediately in the passes run on successors</p>



<a name="207746967"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207746967" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207746967">(Aug 22 2020 at 23:39)</a>:</h4>
<p><span class="user-mention silent" data-user-id="139182">Simon Vandel Sillesen</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Optimization.20of.20const.20array.20access/near/207741037">said</a>:</p>
<blockquote>
<p>Cool. Would that be a good candidate for a mir-opt issue on the issue tracker? I’m guessing with an overall design/mentoring it could be doable as a starter</p>
</blockquote>
<p>I've been waiting to implement this mir-opt as part of my thesis together with @oli's mentoring, but uni hasn't replied to my thesis application yet. Would you be willing to wait a couple more weeks Simon? If they reject my proposal, or if they don't come back to me by then, I would be happy to release this one so that you can implement it.</p>
<p>Can we do that? A two-week deadline? :)</p>



<a name="207759810"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Optimization%20of%20const%20array%20access/near/207759810" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Optimization.20of.20const.20array.20access.html#207759810">(Aug 23 2020 at 06:57)</a>:</h4>
<p><span class="user-mention" data-user-id="212698">@Félix Fischer</span> Of course it’s fine :) let’s all cheer for your uni’s application process</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>